package leetcode.code678;

import java.util.Stack;

public class Solution extends Solution678 {

	private final char L = '(';
	private final char S = '*';

	@Override
	public boolean checkValidString(String s) {
		char[] chars = s.toCharArray();
		Stack<Integer> ls = new Stack<>();
		Stack<Integer> ss = new Stack<>();
		for (int i = 0; i < chars.length; i++) {
			char c = chars[i];
			if (c == L) {
				ls.add(i);
			} else if (c == S) {
				ss.add(i);
			} else {
				if (!ls.isEmpty()) {
					ls.pop();
				} else if (!ss.isEmpty()) {
					ss.pop();
				} else {
					return false;
				}
			}
		}
		if (!ls.isEmpty()) {
			if (ss.size() >= ls.size()) {
				while (!ls.isEmpty()) {
					int li = ls.pop();
					int si = ss.pop();
					if (si < li) {
						return false;
					}
				}
			} else
				return false;
		}
		return true;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
